Covering option discovery has been developed to improve the exploration of RL in single-agent scenarios with sparse reward signals, through connecting the most distant states in the embedding space provided by the Fiedler vector of the state transition graph. Given that joint state space grows exponentially with the number of agents in multi-agent systems, existing researches still relying on single-agent option discovery either become prohibitive or fail to directly discover joint options that improve the connectivity of the joint state space. In this paper, we show how to directly compute multi-agent options with collaborative exploratory behaviors while still enjoying the ease of decomposition. Our key idea is to approximate the joint state space as a Kronecker graph, based on which we can directly estimate its Fiedler vector using the Laplacian spectrum of individual agents' transition graphs. Further, considering that directly computing the Laplacian spectrum is intractable for tasks with infinite-scale state spaces, we further propose a deep learning extension of our method by estimating eigenfunctions through NN-based representation learning techniques.

From left to right, given a graph G with a set of node features F and edge weights Y, the encoder aggregates information from a different number of hops j K away for each nodev G into an embedding vectorc v(j). To do so, it uses a feedforward network to propagate information between different search depths, which is parametrized by a set of weight matrices W j . This embedding vectors are then fed into a differentiable functionφ enc, which sets the parameters,µ k andσ k, of several multidimensional Gaussian distributionsq φ, from where the latent representation of each node in the input graph are sampled from. Variational autoencoders are characterized by a probabilistic generative modelp θ(x z) of the observed variablesx R N given the latent variablesz R M, a prior distribution over the latent variablesp(z) and an approximate probabilistic inference modelq φ (z x). In this characterization,p θ and q φ are arbitrary distributions parametrized by two (deep) neural networksθ and φ and one can think of the generative model as a probabilistic decoder, which decodes latent variables into observed variables, and the inference model as a probabilistic encoder, which encodes observed variables into latent variables. Ideally, if we use the maximum likelihood principle to train a variational autoencoder, we should optimize the marginal log-likelihood of the observed data, i.e., E D [log p θ(x)], wherep D is the data distribution. Unfortunately, computing logp θ(x) requires marginalization with respect to the the latent variablez, which is typically intractable. Therefore, one resorts to maximizing a variational lower bound or evidence lower bound (ELBO) of the log-likelihood the observed data, i.e., max θ max φ E D [ KL(q φ (z x) p(z)) E q φ (z x)log p θ(x z)] . Finally, note that the quality of this variational lower bound (and thus the quality of the resulting V AE) depends on the expressive ability of the approximate inference modelq φ (z x), which is typically assumed to be a normal distribution whose mean and variance are parametrized by a (deep) neural networkφ with the observed datax as an input.

Current multi-view factorization methods make assumptions that are not acceptable for many kinds of data, and in particular, for graphical data with hierarchical structure. At the same time, current hierarchical methods work only in the single-view setting. We generalize the Treelet Transform to the Multi-View Treelet Transform (MVTT) to allow for the capture of hierarchical structure when multiple views are available. Further, we show how this generalization is consistent with the existing theory and how it might be used in denoising empirical networks and in computing the shared response of functional brain data.

In this article we are concerned with the basic but fundamental task of deciding whether a given graph, over which a noisy signal is observed, contains a cluster of anomalous or activated nodes comprising an induced connected subgraph. Such a problem is highly relevant in a variety of scientific areas, such as community detection in social networks, surveillance, disease outbreak detection, biomedical imaging, sensor network detection, gene network analysis, environmental monitoring and malware detection. Recent theoretical contributions in the statistical literature (see, e.g., Arias-Castro et al. [2005, 2008, 2011], Addario-Berry et al. [2010]) have detailed the inherent difficulty of such a testing problem in relatively simplified settings and under specific conditions on the graph topology. From a practical standpoint, the natural algorithm for detection of anomalous clusters of activity in graphs is the the generalized likelihood ratio test (GLRT) or scan statistic, a computationally intensive procedure that entails scanning all well connected clusters and testing individually for anomalous activation. Unfortunately, its performance over general graphs is not well understood, and little attention has been paid to determining alternative, computationally tractable, procedures.

Stochastic Kronecker graphs supply a parsimonious model for large sparse real world graphs. They can specify the distribution of a large random graph using only three or four parameters. Those parameters have however proved difficult to choose in specific applications. This article looks at method of moments estimators that are computationally much simpler than maximum likelihood. The estimators are fast and in our examples, they typically yield Kronecker parameters with expected feature counts closer to a given graph than we get from KronFit. The improvement was especially prominent for the number of triangles in the graph.

How can we model networks with a mathematically tractable model that allows for rigorous analysis of network properties? Networks exhibit a long list of surprising properties: heavy tails for the degree distribution; small diameters; and densification and shrinking diameters over time. Most present network models either fail to match several of the above properties, are complicated to analyze mathematically, or both. In this paper we propose a generative model for networks that is both mathematically tractable and can generate networks that have the above mentioned properties. Our main idea is to use the Kronecker product to generate graphs that we refer to as "Kronecker graphs". First, we prove that Kronecker graphs naturally obey common network properties. We also provide empirical evidence showing that Kronecker graphs can effectively model the structure of real networks. We then present KronFit, a fast and scalable algorithm for fitting the Kronecker graph generation model to large real networks. A naive approach to fitting would take super- exponential time. In contrast, KronFit takes linear time, by exploiting the structure of Kronecker matrix multiplication and by using statistical simulation techniques. Experiments on large real and synthetic networks show that KronFit finds accurate parameters that indeed very well mimic the properties of target networks. Once fitted, the model parameters can be used to gain insights about the network structure, and the resulting synthetic graphs can be used for null- models, anonymization, extrapolations, and graph summarization.